package main

/*
	4,5,6,7,0,1,2
	l     m     r
	1. mid 左右两侧至少有一侧是有序的；nums[0] <= nums[mid] 说明左侧有序，否则右侧有序
	2. 判断 target 是否在有序数组中。若在其中，将查询范围设为有序数组，反之移动另一个指针
*/

func search(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	if len(nums) == 1 {
		if nums[0] == target {
			return 0
		}
		return -1
	}
    l := 0
	r := len(nums) -1
	for l <= r {
		mid:= (l + r) / 2
		if nums[mid] == target {
			return mid
		}
		if nums[0] <= nums[mid] {
			if nums[l] <= target && target < nums[mid] {
				r = mid - 1
			} else {
				l = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[r] {
				l = mid + 1
			} else {
				r = mid - 1
			}
		}
	}
	return -1
}

// func peak(arr []int) int {
// 	left := 0
// 	right := len(arr) - 1
// 	for left < right {
// 		mid := left + (right-left)/2
// 		if arr[mid] < arr[right] {
// 			right = mid
// 		} else {
// 			left = mid + 1
// 		}
// 	}
// 	return left
// }

// func search0(nums []int, target int) int {
// 	left := 0
// 	right := len(nums) - 1
// 	for left <= right {
// 		mid := left + (right-left)/2
// 		if nums[mid] == target {
// 			return mid
// 		} else if nums[mid] > target {
// 			right = mid - 1
// 		} else {
// 			left = mid + 1
// 		}
// 	}
// 	return -1
// }

// func search(nums []int, target int) int {
// 	if len(nums) == 0 {
// 		return -1
// 	}
// 	if len(nums) == 1 {
// 		if nums[0] == target {
// 			return 0
// 		}
// 		return -1
// 	}
// 	pivot := peak(nums)
// 	if nums[0] == target {
// 		return 0
// 	} else if nums[0] > target || pivot == 0 {
// 		ret := search0(nums[pivot:], target)
// 		if ret < 0 {
// 			return ret
// 		}
// 		return pivot + ret
// 	} else {
// 		return search0(nums[0:pivot], target)
// 	}
// }

func main() {
	println(search([]int{1, 3, 5}, 1) == 0)
	println(search([]int{4, 5, 6, 7, 0, 1, 2}, 0) == 4)
	println(search([]int{4, 5, 6, 7, 0, 1, 2}, 5) == 1)
	println(search([]int{4, 5, 6, 7, 0, 1, 2}, 3) == -1)
	println(search([]int{4, 5, 6, 7, 0, 1, 2}, 8) == -1)
	println(search([]int{1, 3}, 3) == 1)
	println(search([]int{4, 5, 6, 7, 0, 1, 2}, 7) == 3)
	println(search([]int{0, 1, 2, 4, 5, 6, 7}, 1) == 1)
	println(search([]int{7, 0, 1, 2, 4, 5, 6}, 0) == 1)
	println(search([]int{1}, 0) == -1)
}
